package h_10_21;

import java.util.HashMap;
import java.util.List;

/**
 * 2841. 几乎唯一子数组的最大和
 * https://leetcode.cn/problems/maximum-sum-of-almost-unique-subarray/description/
 */
public class Main3 {
    public long maxSum(List<Integer> nums, int m, int k) {
        int n = nums.size();
        // 用来统计出现的次数
        HashMap<Integer,Integer> hash = new HashMap<>();
        int count = 0;

        long ret = 0;
        long sum = 0;
        for(int i = 0;i < n;i++) {
            // 入窗口
            sum += nums.get(i);
            // 更新出现的次数
            hash.put(nums.get(i),hash.getOrDefault(nums.get(i),0) + 1);
            if(hash.get(nums.get(i)) == 1) {
                // 在当前的窗口中，第一次出现
                count++;
            }

            // 判断是否满足出窗口 和 更新条件
            if(i < k - 1) {
                continue;
            }

            // 判断是否满足更新条件
            if(count >= m) {
                ret = Math.max(ret,sum);
            }

            // 出窗口
            int out = nums.get(i - k + 1);
            sum -= out;
            // 更新哈希表中的存储个数
            hash.put(out,hash.get(out) - 1);
            if(hash.get(out) == 0) {
                count--;
            }
        }
        return ret;
    }
}
